package one.chapter_2;

/**归并排序
 * 将两个不同的有序数组归并成一个更大的有序数组
 *扩展：
 * 只有2个元素的数组   mid两侧的元素都是有序的。
 */
public class MergeSort extends AbstractSort{
    private Comparable [] aux;
    protected void sort(Comparable[] a) {

      aux=new Comparable[a.length];
      sort(a,0,a.length-1);
    }

    private void sort(Comparable [] a,int lo,int hi){
        if (hi<=lo){
            return;
        }
        int mid=lo+(hi-lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi);
    }

    /**
     *
     * @param a    以mid为界，左右两侧是有序数组
     * @param lo
     * @param mid
     * @param hi
     */
    private void merge(Comparable []a,int lo,int mid,int hi){
        //aux=new Comparable[a.length];
        for (int k=lo;k<=hi;k++){
            aux[k]=a[k];
        }
        int i=lo;
        int j=mid+1;
        for (int k=lo;k<=hi;k++){
            if (i>mid){//左半侧指针位置超过一半，说明左右两侧比较结束了，右侧还有剩余元素
                a[k]=aux[j++];
            }else if (j>hi){//右半侧指针位置超出数组长度，说明左右两侧比较结束了，左侧还有剩余元素
                a[k]=aux[i++];
            }else if (less(aux[j],aux[i])){//左右两侧对应元素进行比较
                a[k]=aux[j++];
            }else {
                a[k]=aux[i++];
            }
        }

    }
}
